class Trie{
public:
    unordered_map<char,Trie*> next;
    bool isEnd = false;                                    
public:
    void insert(string word){
        Trie* cur = this;
        for(char c : word){
            if(!cur->next.count(c)){
                cur->next[c] = new Trie();
            }
            cur = cur->next[c];
        }
        cur->isEnd = true;
    }
    string search(string word){
        Trie* cur = this;
        string path;
        for(char c : word){
            if(!cur->next.count(c)){
                return word;
            }
            path += c;
            cur = cur->next[c];
            if(cur->isEnd){
                return path;
            }
        }
        return word;
    }
};
class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trie* root = new Trie();
        for(auto& s : dictionary){
            root->insert(s);
        }
        
        string ret = "";
        int n = sentence.size();
        for(int i = 0,j = 0;j <= n;j++){
            if(j == n || sentence[j] == ' ' ){
                string word = sentence.substr(i,j-i);
                string path = root->search(word);
                ret += path;
                if(j != n){
                    ret += " ";
                }
                i = j+1;
            }
        }
        return ret;
    }
};
